package 力扣.位运算.异或运算;

import java.util.HashMap;
import java.util.Set;

public class 只出现一次的数136 {
    public static void main(String[] args) {
        int[] ints = {2, 3, 4, 3, 2, 1, 4};
        int i = singleNumber2(ints);
        System.out.println(i);
    }

    /**
     * 使用hash表，或者集合记录出现过的元素
     * @param nums
     * @return
     */
    public static int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (Integer n : nums) {
            if (hash.get(n) == null){//没有出现则记录
                hash.put(n, 1);
            }else
                hash.remove(n);//出现两次则剔除
        }
        Set<Integer> integers = hash.keySet();//最后只剩最后一个元素
        Integer next = integers.iterator().next();
        return next;
    }

    /**
     * 异或运算，异为1 同为0 满足交换律
     * @param nums
     * @return
     */
    public static int singleNumber2(int[] nums) {
        for (int i = 1; i <nums.length ; i++) {
            nums[0]^=nums[i];//正因为满足交换律：将数组中所有元素异或在一起，相同的元素会被异或为0 只剩下不重复的元素
        }
        return nums[0];
    }
}
